package com.yusong.algorithm.array;


import java.util.*;

/**
 * 滑动窗口案例
 */
public class SlidingWindow76 {

    public static void main(String[] args) {
        String s = "A";
        String t = "AA";

        SlidingWindow76 main = new SlidingWindow76();

        String result = main.minWindow(s,t);

        System.out.println(result);
    }


    public String minWindow(String s, String t) {

        char[] arraySource = s.toCharArray();
        int length = arraySource.length;
        if(length < t.length()){
            return "";
        }

        char[] arrayTarget = t.toCharArray();
        Map<Character,Integer> times = new HashMap<>();
        for(char c: arrayTarget){
            if(times.containsKey(c)){
                times.put(c, times.get(c) -1);
            }else {
                times.put(c, 0);
            }

        }

        int leftIndex = 0;
        int rightIndex = -1;

        //缓存
        int cacheMin = length+1;
        int leftMin =  0;
        int rightMin = 0;

        while (leftIndex < (length - t.length() + 1)){
            boolean searchOK = false;
            while (rightIndex < length){
                if(allValid(times)){
                    searchOK = true;
                    break;
                }
                if(rightIndex == length -1){
                    break;
                }
                char nextValue = arraySource[++rightIndex];
                if(!times.containsKey(nextValue)){
                    continue;
                }
                int currentTimes = times.get(nextValue);
                times.put(nextValue, currentTimes+1);
                if(currentTimes > 0){
                    //之前已经出现了
                    continue;
                }
            }
            if(!searchOK){
                //System.out.println(s.substring(leftIndex, rightIndex+1) +"| done" );
                leftIndex++;
                break;
            }
            int currentLength = rightIndex - leftIndex +1;
            //System.out.println(s.substring(leftIndex, rightIndex+1) +"|" +currentLength);
            if(currentLength <cacheMin ){
                cacheMin = currentLength;
                leftMin = leftIndex;
                rightMin = rightIndex;

            }
            // -1
            char leftChar = arraySource[leftIndex];
            if(times.containsKey(leftChar)){
                Integer leftTimes = times.get(leftChar);
                times.put(leftChar, leftTimes -1);
            }
            leftIndex++;
        }
        if( cacheMin == length+1){
            return "";
        }


        return s.substring(leftMin, rightMin+1);
    }

    /**
     * 判断是否所有value >= 1;
     */
    private boolean allValid(Map<Character,Integer> times){
        Set<Character> keySet = times.keySet();
        for (Character c : keySet){
            if(times.get(c) < 1){
                return false;
            }
        }
        return true;
    }





}




/**

 给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。
 输入：S = "ADOBECODEBANC", T = "ABC"
 输出："BANC"
 提示：

 如果 S 中不存这样的子串，则返回空字符串 ""。
 如果 S 中存在这样的子串，我们保证它是唯一的答案。


 **/